import java.util.*;

/**
 * @author LKQ
 * @date 2022/5/22 10:10
 * @description 状态压缩 + 回溯
 */
public class Solution2 {
    public static void main(String[] args) {
        Solution2 solution2 = new Solution2();
        solution2.canIWin(10, 11);
    }
    Boolean[] dp;
    int maxInteger;
    public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
        if ((1 + maxChoosableInteger) * maxChoosableInteger / 2 < desiredTotal) {
            // 所有数都被选完，但是无法达到期望和，两人都无法获胜
            return false;
        }
        maxInteger = maxChoosableInteger;
        dp = new Boolean[1 << maxChoosableInteger];
        return dfs(desiredTotal, 0);
    }

    /**
     *
     * @param desiredTotal 离目标还差多少和
     * @param state [1, max]中每个数被选中的状态，
     * @return
     */
    public boolean dfs(int desiredTotal, int state) {
        if (dp[state] != null) {
            // 如果该状态被标记过，那么返回
            return dp[state];
        }
        for (int i = 1; i <= maxInteger ; i++) {
            // 需要判断当前位是否为1（二进制下）
            int cur = 1 << (i - 1);
            if ((cur & state) == 0) {
                // 当前位为0，代表可以选择
                if (desiredTotal - i <= 0 || !dfs(desiredTotal - i, cur | state)) {
                    return dp[state] = true;
                }
            }
        }
        return dp[state] = false;
    }
}
